package com.cet.programmercarl.algorithmperformancanalysis.二叉树.合并二叉树;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 合并二叉树
 * @author: 陈恩涛
 * @create: 2022-07-28 14:14
 **/
public class LC617 {

    public static void main(String[] args) {

    }

    /**
     * 递归
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }

        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }

    /**
     * 迭代
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        final Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root1);
        deque.offerLast(root2);
        while (!deque.isEmpty()) {
            TreeNode first = deque.pollFirst();
            TreeNode second = deque.pollLast();
            first.val += second.val;

            if (first.right != null && second.right != null) {
                deque.offerFirst(first.right);
                deque.offerLast(second.right);
            }

            if (first.left != null && second.left != null) {
                deque.offerFirst(first.left);
                deque.offerLast(second.left);
            }

            if (first.left == null && second.left != null) {
                // 赋值不再遍历
                first.left = second.left;
            }

            if (first.right == null && second.right != null) {
                first.right = second.right;
            }
        }
        return root1;
    }
}
